#!/usr/bin/env python
#-*- coding:utf-8 -*-

#file: L0Q4.py

import sys

def calc_parity(matrix):
    size = len(matrix)

    parity = True

    for row in matrix:
        value = 0
        for item in row:
            value += item
        parity = parity and (value % 2 == 0)

    for j in range(size):
        value = 0
        for i in range(size):
            value += matrix[i][j]
        parity = parity and (value % 2 == 0)

    return parity

def process_matrix(matrix):
    parity = calc_parity(matrix)
    can_have_parity = None

    if not parity:
        size = len(matrix)
        for i in range(size):
            for j in range(size):
                value = matrix[i][j]

                if value == 0:
                    matrix[i][j] = 1
                else:
                    matrix[i][j] = 0

                can_have_parity = calc_parity(matrix)

                matrix[i][j] = value

                if can_have_parity:
                    return (parity, can_have_parity)

    return (parity, can_have_parity)


def read_input(filename="L0Q4.in"):
    f = open(filename, "r")
    lines = f.readlines()
    f.close()

    matrices = []
    i = 0
    lines_num = len(lines)
    while i < lines_num:
        size = int(lines[i])

        matrix = []
        for j in range(size):
            i += 1
            matrix.append([int(n) for n in lines[i].split(' ')])

        matrices.append(matrix)
        i += 1

    return matrices


def write_output(parity, can_have_parity):
    if parity:
        print 'true'
    else:
        print 'false',
        if can_have_parity:
            print 'possivel'
        else:
            print 'impossivel'


def main():
    if len(sys.argv) > 1:
        input_file = sys.argv[1]
    else:
        input_file = sys.argv[0]
        start = input_file.rfind('/') + 1
        end = input_file.rfind('.py')
        input_file = input_file[start:end] + '.in'

    try:
        input = read_input(input_file)
    except IOError, e:
        print 'Arquivo de entrada "%s" nao encontrado.' % \
                input_file
        sys.exit(1)

    for matrix in input:
        parity, can_have_parity = process_matrix(matrix)
        write_output(parity, can_have_parity)


if __name__ == '__main__':
    main()

